package 动态规划.背包问题;
import java.util.Scanner;

/**
 * 01背包问题是将本行物品和上一行
 * m为背包容量，m物品数量
 * */
public class 完全背包问题优化版 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		long[] dp=new long[m+1];
		int[] w=new int[n+1];
		int[] c=new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			c[i]=sc.nextInt();
		}
		
		for(int x=1;x<=n;x++) {
			for(int y=1;y<=m;y++)	//这里是顺序，01背包是逆序
				if(y>=w[x])
					dp[y]=max(dp[y],dp[y-w[x]]+c[x]);
			/*======打印dp表=======*/
			for(long i:dp)
				System.out.print(i+" ");
			System.out.println();
		}
		
		System.out.println("最多能拿"+dp[m]+"元");
		sc.close();
	}
	
	
	private static long max(long dp, long l) {
		return dp>l?dp:l;
	}
}
